#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <list>

using namespace std;

// 605. 种花问题
class Solution
{
public:
    bool canPlaceFlowers(vector<int> &f, int n) 
    {
        int m = f.size();
        for (int i = 0; i < m; i++) 
        {
            if ((i == 0 || f[i - 1] == 0) && f[i] == 0 && (i == m - 1 || f[i + 1] == 0)) 
            {
                n--;
                i++; // 下一个位置肯定不能种花，直接跳过
            }
        }
        return n <= 0;
    }
};

// 327. 区间和的个数
class BIT
{
private:
    vector<int> tree;

public:
    BIT(int n) : tree(n) {}

    void update(int x, int val)
    {
        while(x < tree.size())
        {
            tree[x] += val;
            x += x & -x;
        }
    }

    int query(int x)
    {
        int ret = 0;
        while(x > 0)
        {
            ret += tree[x];
            x &= x - 1;
        }
        return ret;
    }
};

class Solution 
{
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) 
    {
        int n = nums.size();
        long long sum = 0;
        vector<long long> prefix{0};
        for(int i = 0; i < n; ++i)
        {
            sum += nums[i];
            prefix.push_back(sum);
        }

        set<long long> allNum;
        for(auto x : prefix) 
        {
            allNum.insert(x);
            allNum.insert(x - lower);
            allNum.insert(x - upper);
        }

        unordered_map<long long, int> values;
        int index = 1;
        for(auto x : allNum)
        {
            values[x] = index;
            ++index;
        }

        int ret = 0;
        BIT bit(values.size() + 1);
        for(int i = 0; i < prefix.size(); ++i)
        {
            int left = values[prefix[i] - upper], right = values[prefix[i] - lower];
            ret += bit.query(right) - bit.query(left - 1);
            bit.update(values[prefix[i]], 1);
        }
        return ret;
    }
};

// 406. 根据身高重建队列
class Solution 
{
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) 
    {
        sort(people.begin(), people.end(), [](const auto& a, const auto& b){
            if(a[0] == b[0]) return a[1] < b[1];
            return a[0] > b[0];
        });

        list<vector<int>> ret;
        for(auto& p : people)
        {
            int pos = p[1];
            auto it = ret.begin();
            while(pos--) ++it;
            ret.insert(it, p);
        }
        return vector<vector<int>>(ret.begin(), ret.end());
    }
};